Ngày 29 tháng 6 năm 1995, nhân kỷ niệm ngày lễ bổn mạng Phaolô, Tổng giám mục Bình căn dặn linh mục Inhaxiô Hồ Văn Xuân và linh mục Antôn Phùng Quang Mạnh hoàn tất công trình nhà hành hương Bãi Dâu nhằm phục vụ cho linh mục và giáo dân đến địa điểm này hành hương.[420] Tổng giám mục Phaolô Nguyễn Văn Bình qua đời vài ngày sau đó vào ngày 1 tháng 7, thọ 85 tuổi. Tuy không để lại di chúc, nhưng cố tổng giám mục đã từng căn dặn các linh mục rằng ông không muốn được chôn cất tại Nhà thờ chính tòa, và bày tỏ mong muốn được an táng tại Nhà nguyện của Tiểu chủng viện cũ, vì lý do đó là nơi khởi đầu quá trình tu học của ông.[420] Tòa Thánh Vatican đã gửi điện thư chia buồn đến Tổng giáo phận Thành phố Hồ Chí Minh. Đồng thời, Tòa Thánh cũng tái xác nhận việc bổ nhiệm Giám quản Tông Tòa Huỳnh Văn Nghi.[398] Cái chết của Tổng giám mục Bình không những khiến Tổng giáo phận trống tòa mà còn làm tăng sự khẩn cấp của việc chọn Tổng giám mục kế vị, vốn là tranh cãi lâu dài của Tòa Thánh và chính quyền Việt Nam, kéo dài từ vụ việc bổ nhiệm Tổng giám mục phó Nguyễn Văn Thuận năm 1975.[421]

Linh mục Inhaxiô Hồ Văn Xuân, sau này là Tổng đại diện Tổng giáo phận Thành phố Hồ Chí Minh nhắc đến thời điểm Tổng giám mục Nguyễn Văn Bình qua đời: Linh mục Hồ Văn Xuân và Giuse Mai Thanh Tùng đưa Tổng giám mục Nguyễn Văn Bình trong tình trạng hôn mê rời bệnh viện Thống Nhất vào lúc 4 giờ 30 sáng và về đến Tòa Tổng giám mục 15 phút sau đó. Một giờ sau khi về đến Tòa Tổng giám mục, lúc 5 giờ 45 phút, Tổng giám mục Bình từ trần. Chứng kiến thời khắc lâm chung của tổng giám mục Nguyễn Văn Bình có em gái ông - nữ tu Nguyễn Thị Sanh, linh mục Thư ký Hồ Văn Xuân cùng với hai nữ tu Tổng phụ trách Dòng Mến Thánh Giá Chợ Quán, Gò Vấp và nữ tu Lucia Năng, người chăm sóc sức khỏe riêng cho tổng giám mục Bình. Về phía y bác sĩ có vợ chồng bác sĩ Trương Quang Nhơn, phó giám đốc bệnh viện Thống Nhất, đồng thời là bác sĩ riêng của Nguyễn Văn Bình.[19]

Nhiều giáo dân đã đến viếng thi hài cố Tổng giám mục Nguyễn Văn Bình được quàn tại Nhà thờ Đức Bà Sài Gòn.[422] Ngày 5 tháng 7, lễ an táng cho cố tổng giám mục cử hành tại quảng trường trước Nhà thờ chính tòa Đức Bà Sài Gòn với sự tham dự của 23 giám mục, trong đó có Hồng y Tổng giáo phận Hà Nội Phaolô Giuse Phạm Đình Tụng và Sứ thần Tòa Thánh tại Thái Lan Luigi Bressan, 400 linh mục và khoảng 30.000 giáo dân. Linh cữu cố tổng giám mục được đưa đi chôn cất tại Đại chủng viện Thánh Giuse Sài Gòn theo ước nguyện của ông.[16][423] Đại diện Giáo hoàng Gioan Phaolô II tại tang lễ là Tổng giám mục Luigi Bressan cho biết Giáo hoàng đau buồn và bày tỏ tình hiệp thông với sự ra đi của Tổng giám mục Nguyễn Văn Bình. Đại diện các quan chức Nhà nước và Đảng Cộng sản Việt Nam gửi hoa và điện thư chia buồn. Các đại diện tôn giáo khác như Phật giáo, Tin Lành cũng có lời tôn vinh cố Tổng giám mục Nguyễn Văn Bình.[403] Lễ tang của Tổng giám mục Nguyễn Văn Bình là thánh lễ Công giáo được tổ chức ngoài trời đầu tiên sau khi chế độ chính trị thay đổi ở miền Nam Việt Nam.[393]

Việc tổ chức tang lễ gặp nhiều khó khăn khi Giám quản Nicôla Huỳnh Văn Nghi không được chính quyền chấp nhận, linh mục Tổng đại diện Tổng giáo phận Thành phố Hồ Chí Minh là Gioan Baotixita Huỳnh Công Minh đang chữa bệnh tại Pháp; lúc này linh mục Hồ Văn Xuân nhờ sự hỗ trợ của Giám mục chính tòa giáo phận Cần Thơ Emmanuel Lê Phong Thuận, kiêm Tổng thư ký Hội đồng Giám mục Việt Nam và Giám mục Bartôlômêô Nguyễn Sơn Lâm giúp dàn xếp một số vụ việc trong nội bộ Tổng giáo phận để việc tổ chức tang lễ diễn ra thuận lợi mặc dù các lãnh đạo thành phố Hồ Chí Minh đã tạo nhiều điều kiện. Linh mục Xuân cũng nhắc nhớ đã cộng tác chặt chẽ với linh mục Phêrô Nguyễn Văn Khảm, rồi họ cùng linh mục Giuse Đinh Tất Quý thực hiện cuốn băng video “Giã biệt một Người Cha”, sau đó cho phổ biến rộng rãi.[19]